# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from 树.二叉树.BuildTree import *


class Solution:
    def maxPathSum(self, root: Optional[TreeNode]) -> int:
        inf = float('inf')
        self.max_val = -inf

        def dfs(node: TreeNode):
            """以该点为根节点的左右孩子最大值"""
            if not node: return [0, 0]
            l = dfs(node.left)
            r = dfs(node.right)
            self.max_val = max(self.max_val, node.val, node.val + max(l), node.val + max(r), node.val + max(r) + max(l))
            return [max(node.val, max(l) + node.val), max(node.val, max(r) + node.val)]

        dfs(root)
        return self.max_val


if __name__ == '__main__':
    s = Solution()
    null = None
    root = build_tree_from_level_order([9, 6, -3, null, null, -6, 2, null, null, 2, null, -6, -6, -6])
    r = s.maxPathSum(root)
    print(r)
